package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 1895. 最大的幻方
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/25 18:21
 */
public class LargestMagicSquare {

    private int[][] row;
    private int[][] col;

    public int largestMagicSquare(int[][] grid) {

        int a = grid.length;
        int b = grid[0].length;
        row = new int[a][b];
        col = new int[a][b];
        for (int i = 0; i < a; i++) {
            int[] ints = row[i];
            int[] items = grid[i];
            ints[0] = items[0];
            int item = 0;
            for (int j = 0; j < b; j++) {
                item += items[j];
                ints[j] = item;
            }
        }

        for (int j = 0; j < b; j++) {
            col[0][j] = grid[0][j];
            for (int i = 1; i < a; i++) {
                col[i][j] = col[i - 1][j] + grid[i][j];
            }
        }

        int n = Math.min(a, b);

        for (int k = n; k >= 2; k--) {
            for (int i = 0; i <= a - k; i++) {
                for (int j = 0; j <= b - k; j++) {
                    if (isOk(i, j, k, grid)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }

    private boolean isOk(int i, int j, int k, int[][] grid) {
        int r = i + k - 1;
        int c = j + k - 1;
        int same = row[i][j + k - 1] - row[i][j] + grid[i][j];

        for (int ro = i + 1; ro <= r; ro++) {
            int s = row[ro][j + k - 1] - row[ro][j] + grid[ro][j];
            if (s != same) {
                return false;
            }
        }
        for (int co = j; co <= c; co++) {
            int s = col[i + k - 1][co] - col[i][co] + grid[i][co];
            if (s != same) {
                return false;
            }
        }
        int tmp = 0;
        for (int ro = i, co = j; ro < i + k && co < j + k; ro++, co++) {
            tmp += grid[ro][co];
        }
        if (tmp != same) {
            return false;
        }
        tmp = 0;
        for (int ro = i, co = j + k - 1; ro < i + k && co >= j; ro++, co--) {
            tmp += grid[ro][co];
        }
        return same == tmp;
    }

}
